class Solution {
public:
    vector<int> minBitwiseArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n,-1);
        for(int i = 0; i< n;i++){
            for(int j = 1;j<nums[i];j++){
                if( (j | (j+ 1)) == nums[i])
                {    ans[i] = j;
                    break;
                }
            }
        }
        return ans;
    }
};
class Solution {
public:
// t   10111
//     10110
// t   10001
//      1111
// t   10011
//     10010
//      1 01
//      0 11
// t    0111     +1  1000    ->    1111      去掉连续的最高位的1
//      0001     +1  0010    ->    0011
//       001     +1  0       ->    1001
    vector<int> minBitwiseArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n,-1);
        for(int i = 0; i< n;i++){
            if(nums[i] == 2) continue;
            if(nums[i] == 3){
                ans[i] = 1;
                continue;
            }
            int t = nums[i];
            int tmp = 1;
            for(int j = 0;t;j++){
                if((t >>j &1) == false){
                    // 找到 0了
                    if(j != 0)
                    tmp = nums[i] - (1<<(j-1));
                    break; 
                }
            }
            cout<<tmp<<endl;
            ans[i] = tmp;
        }
        return ans;
    }
};
class Solution {
public:
    int maxRemovals(string source, string pattern, vector<int>& targetIndices) {
        set<int> st(targetIndices.begin(), targetIndices.end());
        int n = source.length(), m = pattern.length();
        vector<vector<int>> memo(n,
                                 vector<int>(m + 1, -1)); // -1 表示没有计算过
        auto dfs = [&](auto&& dfs, int i, int j) -> int {
            if (i < j) {
                return INT_MIN; // 匹配失败
            }
            if (i < 0) {
                return 0;// i = 0 的话一个也不能删
            }
            int& res = memo[i][j + 1];
            if (res != -1) {
                return res;
            }
            // 如果不匹配
            res = dfs(dfs, i - 1, j) + st.count(i);
            // 相等了,可以选,可以不选,取一个最大值
            if (j >= 0 && source[i] == pattern[j]) {
                res = max(res, dfs(dfs, i - 1, j - 1));
            }
            return res;
        };
        // int i = dfs(dfs,n-1,m-1);
        // for(int i = 0;i < n;i++){
        //     for(int j = 0;j<=m;j++){
        //         cout <<memo[i][j]<<' ';
        //     }
        //     cout<<endl;
        // }
        // return i;
        return dfs(dfs, n - 1, m - 1);
    }
};